Monkey Hunter algorithm - Interview question [closed]
Posted
by
Estefany Velez
on Programmers
See other posts from Programmers
or by Estefany Velez
Published on 2012-08-06T16:40:52Z
Indexed on
2012/10/12
9:50 UTC
Read the original article
Hit count: 389
algorithms
|puzzles
Question asked in an Interview:
You are a hunter in the forest. A monkey is in the trees, but you don't know where and you can't see it. You can shoot at the trees, you have unlimited ammunition. Immediately after you shoot at a tree, if the monkey was in the tree, he falls and you win. If the monkey was not in the tree, he jumps (randomly) to an adjacent tree (he has to).
Find an algorithm to get the monkey in the fewest shots possible.
SOLUTION:
The correct answer according to me was in the comments, credit to @rtperson:
You could eliminate this possibility by shooting each tree twice as you sweep left, giving you a worst case of O(2n). EDIT: ...that is, a worst case of O(2n-1). You don't need to shoot the last tree twice.
© Programmers or respective owner
